package  main.java.leetcode.editor.cn;
//2022-11-17 15:14:08
//按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 
//
// n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 
//
// 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 
//
// 
// 
// 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 4
//输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
//解释：如上图所示，4 皇后问题存在两个不同的解法。
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：[["Q"]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 9 
// 
// 
// 
// Related Topics 数组 回溯 👍 1559 👎 0

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

class NQueens {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new NQueens().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    List<List<String>> ans = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        char[][] chars = new char[n][n];
        for(char[] s : chars){
            Arrays.fill(s,'.');
        }
        backtracking(n,0,chars);
        return ans;
    }

    /**
    * @author LazyCat
    * @date  2022/11/20
    * @param
    * @return
     * 回溯
    */
    public void backtracking(int n,int row,char[][] chars){

        if(n == row){
            ans.add(autoList(chars));
            return;
        }
        for(int i = 0;i<n;i++){
            if (pos(row,i,chars,n)){
                chars[row][i] = 'Q';
                backtracking(n,row+1,chars);
                chars[row][i] = '.';
            }
        }
    }
    /**
    * @author LazyCat
    * @date  2022/11/20
    * @param
    * @return
     * Q的位置检验
    */
    public boolean pos(int row,int col,char[][] chars,int n){
        int count = 0;
        //横向确认
        for(int i = 0;i<row;i++){
            if(chars[i][col] == 'Q'){
                return false;
            }
        }
        //45度方向确认
        for(int i = row-1,j = col-1;i>=0&&j>=0;i--,j--){
            if(chars[i][j] == 'Q'){
                return false;
            }
        }
        //135度方向确认
        for(int i = row-1,j = col+1;i>=0 && j<=n-1;i--,j++){
            if(chars[i][j] == 'Q'){
                return false;
            }
        }
        return true;
    }
    /***
    * @author LazyCat
    * @date  2022/11/20
    * @param
    * @return
     * 二维数组转换为List集合
    */
    public ArrayList<String> autoList(char[][] chars){
        ArrayList<String> list = new ArrayList<>();
        for(char[] c : chars){
            list.add(String.copyValueOf(c));
        }
        return list;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
